package com.yuren.codecrushlearn.Q5400;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Created with Intellij IDEA.
 * Description:
 * dph = min(dph - 1, dph + 1)
 * @author 10204
 * @date 2025-06-16 00:08
 */
public class Q5454 {
    public int v;
    public List<List<Integer>> adj;
    public boolean[] visited;

    public Q5454(List<List<Integer>> edges, int e, int v) {
        this.v = v;
        this.adj = new ArrayList<>(v);
        this.visited = new boolean[v];
        for (int i = 0; i < v; i++) {
            adj.add(new ArrayList<>());
        }
        for (List<Integer> edge : edges) {
            addEdge(edge.get(0), edge.get(1));
        }
    }

    public void addEdge(int v1, int v2) {
        adj.get(v1).add(v2);
    }

    public int bfs(int s, int t) {
        if (s == t) return 0;

        int cnt = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(s);
        visited[s] = true;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                int top = queue.poll();
                if (top == t) {
                    return cnt;
                }
                for (int i : adj.get(top)) {
                    if (!visited[i]) {
                        visited[i] = true;
                        queue.add(i);
                    }
                }
            }
            cnt++;
        }
        return -1;
    }

    public int minDist(int s, int t) {
        return bfs(s, t);
    }
}
